package cn.lishiyuan.algorithm.sort;

import java.util.List;

/**
 * 选择排序，
 * <br>
 * 选择排序的的思路是，将列表分成已排序前n项部分和未排序部分
 * <br>
 * 如果我们需要排序 n+1项，那么我们在未排序的部分里面找到最大或者最小的值放到index = n+1这个位置。
 */
public class SelectionSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {

        for (int i = 0; i < data.size(); i++) {
            // 找出最小值然后放到index = i的位置
            int minIndex = i;
            for (int j = i; j < data.size(); j++) {
                // 最小值大于当前值则切换最小值
                if(data.get(minIndex).compareTo(data.get(j)) > 0){
                    minIndex = j;
                }
            }
            if(minIndex != i){
                T t = data.get(i);
                data.set(i, data.get(minIndex));
                data.set(minIndex, t);
            }

        }

        return data;
    }

    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {

        for (int i = 0; i < data.length; i++) {
            // 找出最小值然后放到index = i的位置
             int minIndex = i;
            for (int j = i; j < data.length; j++) {
                // 最小值大于当前值则切换最小值
                if(data[minIndex].compareTo(data[j]) > 0){
                    minIndex = j;
                }
            }
            if(minIndex != i){
                T temp = data[i];
                data[i]=data[minIndex];
                data[minIndex]=temp;
            }
        }

        return data;
    }
}
